Techniques have been developed to increase the amount of information that can be transmitted over communication networks. One conventional approach to increasing network capacity is to install additional network resources to increase overall bandwidth, such as additional routers and cabling. This approach, however, is relatively expensive. Another known approach is to introduce data compression into the network. Data compression typically provides increased data throughput without incurring large costs.
Data compression removes redundancy from a data stream, while preserving data that is essential for reconstructing the original stream at a later point in time. The transmission of compressed data requires not only less bandwidth, but also significantly less time. Therefore, an efficient data compression apparatus permits a communications service provider to expand network capacity at a substantial savings in cost.
A variety of data compression techniques are known. Conventional data compression techniques are classified either as statistical or dictionary-types of data compression. A statistical-type data compression is based on a single symbol coding. Single symbol coding is accomplished by assigning to each possible data symbol in an input data stream a probability for the appearance of that symbol. A symbol is typically represented by a digital value, such as a bit or byte. Examples of statistical data compression include Huffman encoding and the widely published variations of this technique. With Huffman encoding, a symbol having a greater probability of appearance is encoded with a short binary string, while a symbol having a lower probability of appearance in the input data stream is represented by a longer binary string. Although Huffman encoding provides high compression ratios, it requires relatively expensive and complex circuitry. One disadvantage of the statistical-type data compression is that it can require large amounts of memory to buffer the input data and a dictionary.
A dictionary-type data compression algorithm associates groups of consecutive data symbols to dictionary indices. The dictionary-type data compression methods are also commonly referred to as "code book" or "macro coding" approaches. The various code book schemes include the widely known Zif-Lempel (LZ) family of data compression techniques, which are all examples of dictionary-type data compression methods. A typical LZ-type compression method processes an input dat3 stream by checking first if each current input symbol encountered in the data stream matches a symbol already stored in an output buffer. If no match between the input symbol and a previously stored symbol is detected, the input symbol is stored in the output buffer. If, however, a match is detected between the current symbol and the stored data symbol, a pointer indicating a memory location storing a previously received symbol is stored into the buffer instead of the data stream. The LZ methods require a memory buffer for retaining some portion of the input data stream which will be used as a dictionary. In addition, the LZ method requires complex circuitry for generating pointers based on comparisons between stored data and subsequently received symbols.
U.S. Pat. No. 4,701,745 discloses a compression system that replaces a sequence of repetitive bytes in a data stream with an identification signal that indicates the location and length of a previous occurrence of the bytes in the data stream. However, this system also requires a memory buffer for temporarily storing the prior occurrence of the repetitive sequence.
The inclusion of additional memory buffers and circuitry to process input data increases the size, cost, and power dissipation of a compression system.
Another drawback of the above-described compression algorithms is that they typically require a processor for their execution. In a communications system using a central processor, these compression algorithms can consume precious computational resources and negatively affect the system's overall performance.
Therefore, there is a need for a data compression apparatus that does not strain limited computational resources and is simple to implement in digital circuitry without a large amount of memory and does not introduce additional delays.